package 中等.模拟;

import java.util.*;

/**
 * 给你一个字符串 s ，其中包含字母
 * 顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。
 * <p>
 * s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
 * s 保证是一个符合题目要求的字符串
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english
 */
public class 从英文中重建数字_423 {

    public static void main(String[] args) {

        String str = "fivefour";
        System.out.println(efficientOriginalDigits(str));

    }

    /**
     * zero，one，two，three，four，five，six，seven，eight，nine
     * 从上面这些英文数字中，随机取一个或者多个，组成字符串，然后打乱字符
     * 例如：one,two->oentow->1,2
     * 对应表格
     * ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]
     * - 0   8   4   5   3   0   1   6   0   4   2   2   5   6   0
     * - 1       5   6   8   1   7   7   3       3       7
     * - 3           8       2   9       4       8
     * - 5           9       4
     * - 7
     * - 8
     * - 9
     * 步骤：
     * 1，先将字符串中相同字符个数记录在数组中
     * 2，发现，g，u，w，x，z可以直接确定，取出来
     *
     * @param s
     * @return
     */
    public static String originalDigits(String s) {
        List<Integer> container = new ArrayList<>();
        int[] letters = new int[26];
        for (int i = 0; i < s.length(); i++) {
            letters[s.charAt(i) - 'a']++;
        }
        //g，u，w，x，z
        for (int i = 1; i <= letters['g' - 'a']; i++) {
            container.add(8);
            letters['e' - 'a']--;
            letters['i' - 'a']--;
            letters['h' - 'a']--;
            letters['t' - 'a']--;
        }
        for (int i = 1; i <= letters['u' - 'a']; i++) {
            container.add(4);
            letters['f' - 'a']--;
            letters['o' - 'a']--;
            letters['r' - 'a']--;
        }
        for (int i = 1; i <= letters['w' - 'a']; i++) {
            container.add(2);
            letters['t' - 'a']--;
            letters['o' - 'a']--;
        }
        for (int i = 1; i <= letters['x' - 'a']; i++) {
            container.add(6);
            letters['s' - 'a']--;
            letters['i' - 'a']--;
        }
        for (int i = 1; i <= letters['z' - 'a']; i++) {
            container.add(0);
            letters['e' - 'a']--;
            letters['r' - 'a']--;
            letters['o' - 'a']--;
        }

//     * 表格->
//     * ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]
//     * -             5   3       1                       5
//     * - 1       5           1   7   7   3       3       7
//     * - 3                       9
//     * - 5           9
//     * - 7
//     * - 9

        //发现f，t,r，o可以确定，t,r任意一个可以确定3
        for (int i = 1; i <= letters['f' - 'a']; i++) {
            container.add(5);
            letters['i' - 'a']--;
            letters['v' - 'a']--;
            letters['e' - 'a']--;
        }
        for (int i = 1; i <= letters['t' - 'a']; i++) {
            container.add(3);
            letters['h' - 'a']--;
            letters['r' - 'a']--;
            letters['e' - 'a']--;
            letters['e' - 'a']--;
        }
        for (int i = 1; i <= letters['o' - 'a']; i++) {
            container.add(1);
            letters['t' - 'a']--;
            letters['w' - 'a']--;
        }
//     * 表格->
//     * ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]
//     * -
//     * -                         7   7                   7
//     * -                         9
//     * -             9
//     * - 7
//     * - 9

        //发现i，v可以确定
        for (int i = 1; i <= letters['i' - 'a']; i++) {
            container.add(9);
            letters['t' - 'a']--;
            letters['w' - 'a']--;
        }
        for (int i = 1; i <= letters['v' - 'a']; i++) {
            container.add(7);
        }

        Integer[] sortNums = container.toArray(new Integer[container.size()]);
        Arrays.sort(sortNums);
        StringBuilder builder = new StringBuilder();
        for (Integer curNum : sortNums) {
            builder.append(curNum);
        }
        return builder.toString();
    }

    /**
     * 用哈希表来存字符出现的个数
     * 对应表格
     * ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]
     * - 0   8   4   5   3   0   1   6   0   4   2   2   5   6   0
     * - 1       5   6   8   1   7   7   3       3       7
     * - 3           8       2   9       4       8
     * - 5           9       4
     * - 7
     * - 8
     * - 9
     * 步骤：
     * 1，将某个元素出现的次数用哈希表存储起来
     * 例子
     * 求5出现的次数，f和v都行
     * f->  f出现的次数-4出现的次数
     *
     * @param s
     * @return
     */
    public static String efficientOriginalDigits(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        //索引相当于数字0-9，索引所在的值是出现次数，无需排序
        int[] ints = new int[10];
        //g，u，w，x，z，84260
        ints[8] = map.getOrDefault('g', 0);
        ints[4] = map.getOrDefault('u', 0);
        ints[2] = map.getOrDefault('w', 0);
        ints[6] = map.getOrDefault('x', 0);
        ints[0] = map.getOrDefault('z', 0);

        //f，h，v，537
        ints[5] = map.getOrDefault('f', 0) - ints[4];
        ints[3] = map.getOrDefault('h', 0) - ints[8];
        ints[7] = map.getOrDefault('v', 0) - ints[5];

        //i，9
        ints[9] = map.getOrDefault('i', 0) - ints[5] - ints[6] - ints[8];

        //n，1
        ints[1] = map.getOrDefault('n', 0) - ints[7] - ints[9] * 2;

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < ints.length; i++) {
            for (int j = 1; j <= ints[i]; j++) {
                stringBuilder.append(i);
            }
        }
        return stringBuilder.toString();
    }

}
